import java.util.HashMap;
import java.util.Map;

class Solution {

    // 位1的个数
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((1<<i) & n) != 0) { // 这个位是1
                count++;
            }
        }
        return count;
    }

    // 只出现一次的数字
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }

    // 只出现一次的数字III
    public int[] singleNumber2(int[] nums) {
        // 暴力枚举：哈希表统计
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], hash.getOrDefault(nums[i], 0) + 1);
        }
        int[] ret = new int[2];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (hash.get(nums[i]) == 1) {
                ret[j++] = nums[i];
            }
        }
        return ret;
    }

    // 只出现一次的数字III(优化版)
    public int[] singleNumber3(int[] nums) {
        // 先分组，再分别统计
        int[] ret = new int[2];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum ^= nums[i]; // 这个是两个数字的异或结果
        }
        // 找到两个数字有区别的地方进行分组
        int mask = sum & (-sum); // 找到最右边第一个出现的1
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & mask) == 0) {
                ret[0] ^= nums[i];
            } else {
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }

    // 比特位计数
    public int[] countBits(int n) {
        int[] ret = new int[n+1];
        for (int i = 0; i <= n; i++) {
            // 统计每一个数中二进制位1的个数
            int count = 0;
            int temp = i;
            // 更高效：只统计1的个数，不关注0
            while (temp != 0) {
                count++; // 此时temp中还有1，直接统计
                temp = (temp & (temp-1)); // 去掉最右边的1
            }

            // // 这样可以避免每次循环32次
            // while (temp != 0) {
            //     if ((temp & 1) != 0) {
            //         count++;
            //     }
            //     temp >>= 1;
            // }

            // for (int j = 0; j < 32; j++) {
            //     if (((temp>>j) & 1) != 0) {
            //         count++;
            //     }
            // }
            ret[i] = count;
        }
        return ret;
    }

}